package com.shm.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 17. 电话号码的字母组合
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
 *
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 *
 *
 * 示例:
 *
 * 输入："23"
 * 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 * 说明:
 * 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
 * @author SHM
 */
public class LetterCombinations {

    /**
     * 方法一：回溯
     * 首先使用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作。
     *
     * 回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）。该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。然后进行回退操作，遍历其余的字母排列。
     *
     * 回溯算法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(3^m \times 4^n)O(3
     * m
     *  ×4
     * n
     *  )，其中 mm 是输入中对应 33 个字母的数字个数（包括数字 22、33、44、55、66、88），nn 是输入中对应 44 个字母的数字个数（包括数字 77、99），m+nm+n 是输入数字的总个数。当输入包含 mm 个对应 33 个字母的数字和 nn 个对应 44 个字母的数字时，不同的字母组合一共有 3^m \times 4^n3
     * m
     *  ×4
     * n
     *   种，需要遍历每一种字母组合。
     *
     * 空间复杂度：O(m+n)O(m+n)，其中 mm 是输入中对应 33 个字母的数字个数，nn 是输入中对应 44 个字母的数字个数，m+nm+n 是输入数字的总个数。除了返回值以外，空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输入无关，可以看成常数，递归调用层数最大为 m+nm+n。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/
     * @param digits
     * @return
     */
    public List<String> letterCombinations(String digits) {
        HashMap<Character,char[]> map = new HashMap<>(8);
        map.put('2',new char[]{'a','b','c'});
        map.put('3',new char[]{'d','e','f'});
        map.put('4',new char[]{'g','h','i'});
        map.put('5',new char[]{'j','k','l'});
        map.put('6',new char[]{'m','n','o'});
        map.put('7',new char[]{'p','q','r','s'});
        map.put('8',new char[]{'t','u','v'});
        map.put('9',new char[]{'w','x','y','z'});

        List<String> res = new ArrayList<>();
        if ((digits.length() == 0)){
            return res;
        }
        backtrack(res,map,digits,0,new StringBuffer());
        return res;
    }

    public void backtrack(List<String> res,HashMap<Character,char[]> map,String digits,int index,StringBuffer stringBuffer){
        if (index == digits.length()){
            res.add(stringBuffer.toString());
        }else{
            char[] chars = map.get(digits.charAt(index));
            for (int i = 0; i < chars.length; i++) {
                stringBuffer.append(chars[i]);
                backtrack(res,map,digits,index+1,stringBuffer);
                stringBuffer.deleteCharAt(index);
            }
        }
    }
}
